package sysu.el.graph.undi.algor;

import java.util.ArrayList;
import java.util.Arrays;

import sysu.el.array.BoolArray;
import sysu.el.array.ints.ArrInt;
import sysu.el.array.ints.ArrQueueInt;
import sysu.el.graph.undi.UndiGT;

/**
 * Algorithm: Flood Fill Algorithm
 * @author Edwin
 *
 */
public class ConnectedBranchSearcher {
	public UndiGT graph;
	public BoolArray visitedTag; // Just for the chain memeber
//	public ArrInt branch;
	
	// The element is the reduced version of the array
	public ArrayList<int[]> branches;
	public ArrQueueInt queue;
	
	public ConnectedBranchSearcher(UndiGT g){
		graph = g;
		visitedTag = new BoolArray(g.getNodeNum());
//		branch = new ArrInt(g.getNodeNum() + 1);
		branches = new ArrayList<int[]>();
		queue = new ArrQueueInt(g.getNodeNum() + 1);
	}
	
	public void startSearching(int node){
		queue.reset();
		queue.add(node);
		visitedTag.setVisited(node);
		while (queue.isEmpty() == false){
			int cur = queue.forward();
			int[] adj = graph.getList(cur);
			for (int e : adj){
				if (visitedTag.isUnvisited(e)){
					queue.add(e);
					visitedTag.setVisited(e);
				}
			}
		}
		int[] sortedQ = queue.toArray();
		Arrays.sort(sortedQ);
		branches.add(sortedQ);
	}
	
	public void searching(){
		branches.clear();
		visitedTag.reset();
		for (int i=0; i<graph.getNodeNum(); i++){
			if (visitedTag.isVisited(i)) continue;
			this.startSearching(i);
		}
	}

}
